package main.java.indi.zyj.coderecord;

import java.util.Deque;
import java.util.LinkedList;

public class _07_maxAreaOfIsland {


    boolean[][] visited;
    int count = 0;
    int[][] location = {
            {0, 1}, //right
            {1, 0}, //down
            {0, -1}, //left
            {-1, 0} //up
    };


    public int maxAreaOfIsland(int[][] grid) {

        int res = 0;
        visited = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    Bfs(grid, i, j);
                    res = Math.max(res, count);
                }
            }
        }

        return res;

    }

    private void Bfs(int[][] grid, int x, int y) {

        Deque<int[]> queue = new LinkedList<>();

        queue.add(new int[]{x, y});
        visited[x][y] = true;
        count++;

        while (!queue.isEmpty()){
            int[] loc = queue.poll();
            int m = loc[0], n = loc[1];
            for (int i = 0; i < 4; i++) {
                int nextX = m + location[i][0];
                int nextY = n + location[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                    continue;
                }
                if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                    visited[nextX][nextY] = true;
                    queue.offer(new int[]{nextX, nextY});
                    count++;
                }

            }
        }

    }


}
